# -*- coding: utf-8 -*-            
# @Time : 2022/11/22 22:52
# @Author  : lining
# @FileName: 串联所有单词的子串.py
"""
https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联字串在 s 中的开始索引。你可以以 任意顺序 返回答案。
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

解题思路：
（1）因为每个单词的长度都是固定的a，从给定的字符串从当前位置取出n长度的串，分割成长度为a的n歌单词，排序，拼成字符串，和给定的单词进行比较是否一致
（2）字符串的比较是每个字符一次比较，性能会很差，优化，改成用map，把每个单词左key，出现的次数做value，两个map进行比较
优化:
（1）按照k长度切分字符串，使用滑动窗口，从左到右扫描字符串,不满长度k的就删除，和目标字符串进行比较map是否相等
s = '123456789'  k=2   s_split = ['12', '34', '56', '78']
"""

class Solution(object):
    def findSubstring(self, s, words):
        """
        s = "barfoothefoobarman", words = ["foo","bar"]
        :param s: 字符串
        :param words: 目标字符串
        :return:
        """
        # 每个单词长度
        k = len(words[0])
        # words的单词个数
        len_words = len(words)
        # s的长度
        len_s = len(s)
        # 保存单词开始的位置
        position = []
        # 目标单词的字典
        words_dict = self.list_to_dict(words)
        if len_s < k*len_words:
            return position
        for i in range(0, len_s):
            if i>0 and i%k == 0:
                continue
            # 滑动窗口
            s_dict = {}
            s_new = s[i:]
            # k为长度进行分割--------可以直接用下标去操作，而不是生成一个迭代器
            s_split = (s_new[x:x+k] for x in range(0, len(s_new), k) if x+k<=len(s_new))
            # if len(s_split) < len_words:
            #     break
            # 数据顺序栈
            s_list = []
            for y, z in enumerate(s_split):
                s_list.append(z)
                if z in s_dict:
                    s_dict[z] = s_dict[z]+1
                else:
                    s_dict[z] = 1
                # 滑动窗口长度和目标窗口长度一样（1）进行比较，（2）保存位置，（3）删除第一个key，
                if len(s_list) == len_words:
                    result = self.compare_dict(s_dict, words_dict)
                    # 和目标words相同，添加一个位置
                    if result:
                        position.append(i+(y+1)*k-k*len_words)
                    # s_dict.pop(list(s_dict.keys())[0])
                    # 删除第一个key（1）正常的串，每一个单词进来，原来的字典里都是没有的
                    #（2）当前进来的key已经存在字典中
                    # [1]这个key是s_dict的第一个key,第一个key-1
                    # [2]这个key不是s_dict的第一个key，删除第一个key
                    # (3)key的值为复数，需要在第一个key-1
                    # 问题：没有记录进入的顺序，有重复个数，怎么知道要删除哪个
                    first_key = s_list[0]
                    del s_list[0]
                    if s_dict[first_key]>1:
                        s_dict[first_key] = s_dict[first_key] - 1
                    else:
                        s_dict.pop(first_key)
        print(position)

    def list_to_dict(self, words):
        """把列表转字典"""
        list_dict = {}
        for i in words:
            if i in list_dict:
                list_dict[i] = list_dict[i]+1
            else:
                list_dict[i] = 1
        return list_dict

    def compare_dict(self, dict1, dict2):
        """比较两个字典是否相同"""
        for key in dict1:
            if key not in dict2 or dict1[key] != dict2[key]:
                return
        return True


# s = "barfoothefoobarman"
# words = ["foo","bar"]
# s = "wordgoodgoodgoodbestword"
# words = ["word","good","best","word"]
# s = "barfoofoobarthefoobarman"
# words = ["bar","foo","the"]
# s = "wordgoodgoodgoodbestword"
# words = ["word","good","best","good"]
# 重复插入数据
# s = "lingmindraboofooowingdingbarrwingmonkeypoundcake"
# words = ["fooo","barr","wing","ding","wing"]
# s = "aaa"
# words = ["a","a"] #0,1
s = 'barfoofoobarthefoobarman'# 6,9,12
words = ["bar","foo","the"]
# s ="bcabbcaabbccacacbabccacaababcbb"
# words = ["c","b","a","c","a","a","a","b","c"]    #[6,16,17,18,19,20]
Solution().findSubstring(s, words)
